package cn.bellychang.leetcode.question234;

/**
 * Given a singly linked list, determine if it is a palindrome.
 * <p>
 * Follow up:
 * Could you do it in O(n) time and O(1) space?
 *
 * @author ChangLiang
 * @date 2021/2/3
 */
public class Solution2 {

    public boolean isPalindrome(ListNode head) {



        if (head==null || head.next == null) {
            return true;
        }

        // 两个指针 fast指针每次走两步 slow指针每次走一步
        // 并且slow指针每走一步 要把链表反转过来
        // slow指针走到中间 再启动两个指针 向两侧走 比较

        ListNode fast = head;
        ListNode prev;
        ListNode curr = head;
        ListNode next = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            if (fast != null) {
                prev = curr;
                curr = next;
                next = curr.next;
                curr.next = prev;
            }

        }

        if (fast == null) {
            return isSame(curr, next);
        } else {
            return isSame(curr.next, next);
        }
    }

    private boolean isSame(ListNode left, ListNode right) {
        while (left != null && right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }
}
